/*
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]
*/

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int> > matrix;
        matrix.resize(n);
        for (int i = 0; i < n; i++) matrix[i].resize(n, 0);
        int x = 0, y = 0, num=0;
        while (n>0) {
            // scan through right, down, left, up
            for (int steps=n-1;steps>0;steps--) matrix[x][y++] = ++num;
            for (int steps=n-1;steps>0;steps--) matrix[x++][y] = ++num;
            for (int steps=n-1;steps>0;steps--) matrix[x][y--] = ++num;
            for (int steps=n-1;steps>0;steps--) matrix[x--][y] = ++num;
            if (n==1) matrix[x][y] = ++num;
            // make a down right turn
            x++;y++; n -= 2;
        }
        return matrix;
    }
};
